UVa/12322 - Handgun Shooting Sport/12322.3.cpp

   1 // Accepted, trying to make it run faster.
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <bitset>
  14 #include <string>
  15 #include <cstdio>
  16 #include <vector>
  17 #include <cmath>
  18 #include <queue>
  19 #include <deque>
  20 #include <stack>
  21 #include <list>
  22 #include <map>
  23 #include <set>
  24
  25 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define D(x) cout << #x " is " << x << endl
  28
  29 namespace IO {
  30 #define MAXBUFF (1<<20)
  31    char buffer[MAXBUFF], *p = buffer+MAXBUFF;
  32    char buffer2[MAXBUFF], *p2 = buffer2;
  33
  34    inline char read_char() {
  35       if( p == buffer+MAXBUFF ) {
  36          fread( buffer, 1, MAXBUFF, stdin );
  37          p = buffer;
  38       }
  39       return *p++;
  40    }
  41
  42    inline int read_int() {
  43       char c = read_char();
  44       while( !isdigit(c) and c != '-' ) c = read_char();
  45       int sign = c == '-' ? -1 : +1;
  46       if (c == '-') c = read_char();
  47       int ret = c-'0';
  48       while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
  49       return ret * sign;
  50    }
  51
  52    void flush() {
  53       fwrite( buffer2, 1, p2-buffer2, stdout );
  54       p2 = buffer2;
  55    }
  56
  57    inline void write( char c ) {
  58       if( p2 == buffer2+MAXBUFF ) {
  59          fwrite( buffer2, 1, MAXBUFF, stdout );
  60          p2 = buffer2;
  61       }
  62       *p2++ = c;
  63    }
  64 }
  65
  66 struct point {
  67     int x, y;
  68     point(){} point(int x, int y) : x(x), y(y) {}
  69     bool operator < (const point &t) const {
  70         return x * t.y - y * t.x > 0;
  71     }
  72     bool operator == (const point &t) const {
  73         return x * t.y - y * t.x == 0;
  74     }
  75     bool operator <= (const point &t) const {
  76         return *this < t or *this == t;
  77     }
  78     bool operator != (const point &t) const {
  79         return !(*this == t);
  80     }
  81 };
  82
  83 typedef pair< point, point > interval;
  84
  85 // Returns true if interval 'a' is strictly included in interval 'b'
  86 inline bool included(const interval &a, const interval &b) {
  87     return b.first < a.first and a.second < b.second;
  88 }
  89
  90 const int MAXN = 1001;
  91
  92 interval intervals[MAXN];
  93 int B;
  94
  95 inline void delete_redundant() {
  96     bitset<MAXN> deleted;
  97     for (int i = 0; i < B; ++i) {
  98         for (int j = 0; j < B; ++j) {
  99             // delete interval i if interval j is completely inside it
 100             if (included(intervals[j], intervals[i])) {
 101                 deleted[i] = true;
 102                 break;
 103             }
 104         }
 105     }
 106     int k = 0;
 107     for (int i = 0; i < B; ++i) {
 108         if (!deleted[i]) {
 109             intervals[k++] = intervals[i];
 110         }
 111     }
 112     B = k;
 113 }
 114
 115 char buf[10];
 116
 117 int main(){
 118     while (B = IO::read_int()) {
 119         for (int i = 0; i < B; ++i) {
 120             point p1, p2;
 121             intervals[i].first.x = IO::read_int();
 122             intervals[i].first.y = IO::read_int();
 123             intervals[i].second.x = IO::read_int();
 124             intervals[i].second.y = IO::read_int();
 125             if (intervals[i].second < intervals[i].first) swap(intervals[i].first, intervals[i].second);
 126         }
 127         //printf("Before removing redundant B is %d\n", B);
 128         delete_redundant();
 129         sort(intervals, intervals + B);
 130         //printf("After removing redundant B is %d\n", B);
 131
 132         //printf("Before removing duplicates B is %d\n", B);
 133         B = unique(intervals, intervals + B) - intervals;
 134         //printf("After removing duplicates B is %d\n", B);
 135
 136         int ans = 0, i = 0;
 137         while (i < B) {
 138             ans++;
 139             point pick = intervals[i].second;
 140             while (i < B and intervals[i].first <= pick) i++;
 141         }
 142         sprintf(buf, "%d\n", ans);
 143         for (char * c = buf; *c; ++c) IO::write(*c);
 144     }
 145     IO::flush();
 146     return 0;
 147 }